SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Livewire Segmentation Technique</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Livewire Segmentation Technique</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p><b>Livewire</b>, is a segmentation technique which allows a user to select regions of interest to be extracted quickly and accurately, using simple mouse clicks.<sup id="cite_ref-Baggio2007_1-0" class="reference"><a href="#cite_note-Baggio2007-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It is based on the <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">lowest cost path algorithm</a>, by <a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Edsger W. Dijkstra</a>. Firstly convolve the image with a <a href="Sobel_operator" title="Sobel operator">Sobel filter</a> to extract edges. Each pixel of the resulting image is a vertex of the graph and has edges going to the 4 pixels around it, as up, down, left, right. The edge costs are defined based on a cost function. In 1995, Eric N. Mortensen and William A. Barrett made some extension work on livewire segmentation tool, which is known as Intelligent Scissors.<sup id="cite_ref-MORTENSEN1995_2-0" class="reference"><a href="#cite_note-MORTENSEN1995-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Livewire_segmentation">Livewire segmentation</h2></div>

<p>The user sets the starting point clicking on an image's pixel, known as an anchor. Then, as he starts to move the mouse over other points, the smallest cost path is drawn from the anchor to the pixel where the mouse is over, changing itself if the user moves the mouse. If he wants to choose the path that is being displayed, he simply clicks the image again.

</p><p>One can easily see in the right image, that the places where the user clicked to outline the desired region of interest are marked with a small square. It is also easy to see that the livewire has snapped on the image's borders.

</p>

<div class="mw-heading mw-heading2"><h2 id="Livewire_algorithm">Livewire algorithm</h2></div>

<p>Convolve the image with a Sobel filter to extract edges. Using this filtered image create a graph using pixels as nodes with edges in four directions (up, down, left right).<sup id="cite_ref-Baggio2007_1-1" class="reference"><a href="#cite_note-Baggio2007-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Edges are weighted with features gathered from the Sobel filter making it less costly to stay on an edge. Several different cost methods are possible but the most important is the gradient magnitude<sup id="cite_ref-Baggio2007_1-2" class="reference"><a href="#cite_note-Baggio2007-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p><b>Live-Wire 2-D DP graph search algorithm in pseudocode</b> <sup id="cite_ref-MORTENSEN1995_2-1" class="reference"><a href="#cite_note-MORTENSEN1995-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>algorithm</b> Livewire <b>is</b>

<b>input:</b>

<i>s</i> {Start (or seed) pixel.}

l(<b>q, r</b>) {Local cost function for link between pixels q and r.}

<b>data structures:</b>

L {List of active pixels sorted by total cost (initially empty).}

N(<b>q</b>) {Neighborhood set of q (contains 8 neighbors of pixel).}

e(<b>q</b>) {Boolean function indicating if q has been expanded/processed.}

g(<b>q</b>) {Total cost function from seed point to q.}

<b>output:</b>

<i>p</i> {Pointers from each pixel indicating the minimum cost path.}

g(s) ← 0; L ← s; {Initialize active list with zero cost seed pixel.}

<b>while</b> L≠∅ <b>do begin</b> {While still points to expand.}

<b>q</b> ← min(L); {Remove minimum cost pixel q from active list.}

e(<b>q</b>) ← TRUE; {Mark q as expanded (i.e., processed).}

<b>for each</b> r∈N(q) <b>such that</b> not e(<b>r</b>) <b>do begin</b>

gtmp ←g(<b>q</b>) + l(<b>q, r</b>); {Compute total cost to neighbor.}

<b>if</b> r<b>∈L</b> <b>and</b> gtmp < g(<b>r</b>) <b>then</b> {Remove higher cost neighbor's from list.}

r ← L;

<b>if</b> r∉L <b>then begin</b> {If neighbor not on list, }

g(<b>r</b>) ← gtmp; {assign neighbor's total cost, }

p(<b>r</b>) ← <b>q</b>; {set (or reset) back pointer, }

L ← <b>r</b>; {and place on (or return to) active list.}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Extension_to_3D">Extension to 3D</h2></div>

<p>In 2010, Leo Grady extended the Livewire algorithm to 3D.<sup id="cite_ref-GRADY2010_3-0" class="reference"><a href="#cite_note-GRADY2010-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This extension treated the 2D Livewire algorithm as enabling a user to specify a 0-dimensional boundary (two points) and finding the minimal 1-dimensional coboundary (curve) connecting those points, where the minimum is defined in terms of image properties. In order to extend the algorithm to 3D, the user is instead asked to specify one or more 1-dimensional boundaries (closed curves) and the algorithm finds the minimal 2-dimensional coboundary (surface) bounded by the 1-dimensional curves, where the minimum surface is defined in terms of image properties. This 3D extension of Livewire leans heavily on concepts of <a href="Discrete_exterior_calculus" title="Discrete exterior calculus">discrete exterior calculus</a> to reinterpret the 2D Livewire algorithm from the standpoint of boundary/coboundary operators and then apply these concepts in 3D. An efficient algorithm for computing the 3D minimal surface is also provided in the Grady paper.

</p>

<ul><li><a href="Segmentation_(image_processing)" class="mw-redirect" title="Segmentation (image processing)">Segmentation</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<li id="cite_note-Baggio2007-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Baggio2007_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Baggio2007_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Baggio2007_1-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">BAGGIO, Daniel L´elis. GPGPU Based Image Segmentation Livewire Algorithm Implementation. 2007. 108f. Thesis of Master in Science – Technological Institute of Aeronautics, S˜ao Jos´e dos Campos. <a rel="nofollow" class="external free" href="http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf">http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20101217223840/http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf">Archived</a> 2010-12-17 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></span>

</li>

<li id="cite_note-MORTENSEN1995-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-MORTENSEN1995_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-MORTENSEN1995_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">MORTENSEN, E. N.; BARRETT, W. A. Intelligent scissors for image composition. In: SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. New York, NY, USA: ACM Press, 1995. p. 191–198. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-701-4</bdi>.</span>

</li>

<li id="cite_note-GRADY2010-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-GRADY2010_3-0">^</a></b></span> <span class="reference-text">Leo Grady, “<a rel="nofollow" class="external text" href="http://leogrady.net/wp-content/uploads/2017/01/grady2010minimal.pdf">Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D</a>”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 2, pp. 321-334, Feb. 2010</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://ivussnakes.sourceforge.net">Open Source Java implementation of Livewire Image Segmentation Tool for ImageJ - Daniel Lelis Baggio</a></li>

<li><a rel="nofollow" class="external text" href="http://ivussnakes.sourceforge.net/?q=node/22">Coronary Segmentation video</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/pdyban/livewire">Open source Python implementation</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-01-21" href="https://en.wikipedia.org/wiki/?title=Livewire_Segmentation_Technique&oldid=1134909642">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>